"""
给你一个字符串 s 和一个字符串列表 wordDict 作为字典，判定 s 是否可以由空格拆分为一个或多个在字典中出现的单词。

说明：拆分时可以重复使用字典中的单词。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-break
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""

class Solution:
    def wordBreak(self, s: str, wordDict: [str]) -> bool:
        n = len(s)
        dp = [False] * (n+1)
        dp[0] = True
        word_set = set(wordDict)
        for i in range(n+1):
            for j in range(i):
                if dp[j] and word_set.__contains__(s[j:i]):
                    dp[i] = True
                    break
        return dp[n]